2023 江苏省数据安全竞赛

Van1sh 比赛小屋 Write Up

创建时间:2023-09-17 11:21

字数:1.4k 阅读:

题目内容
解题步骤
解题脚本

昨儿下午参加了一下首届江苏省数据安全竞赛，虽然密码学的题目有缝合怪之嫌，但涉及的知识点却也并不简单。但这是第一届比赛，面向的对象还是全省范围内的职工、学生、教师，CTF现在真卷啊。。。

[TOC]

题目内容

from Crypto.Util.number import *

def pad(msg):
    return msg + b'\x00' * (2048 // 8 - len(msg))


def day():
    print("# == Day Time == #")
    A = [getRandomRange(1 << 30, 1 << 40) for _ in '01234']

    from notebook import pubkeys
    hint = str(A)[1:-1].replace(', ', '||').encode()
    hint = bytes_to_long(pad(hint))
    package = []
    for pubkey in pubkeys:
        e, n = pubkey
        package.append(pow(hint, e, n))
    print(f"{package = }")

    return A


def night(A):
    print("# == Night Time == #")
    from secrets import secret

    p, q = [getPrime(1024) for _ in '01']
    e, n = 0x10001, p * q
    message = bytes_to_long(pad(secret))
    ciphertext = pow(message, e, n)
    print(f"{e = }")
    print(f"{n = }")
    print(f"{ciphertext = }")

    core = getRandomRange(1 << 70, 1 << 80)
    box = (A[4] * p ** 4 + A[3] * p ** 3 + A[2] * p ** 2 + A[1] * p ** 1 + core) % n
    shell = (A[4] * box ** 4 + A[3] * box ** 3 + A[2] * box ** 2 + A[1] * box ** 1 + A[0]) % n
    print(f"{shell = }")

A = day()
night(A)

题目输出

# notebook.pubkeys
pubkeys = [
    [13, 16966923273393034574368601955241184391111444785998466710722972275633988040568029224272430397635357872449163107278928804572765398970752644900568552514020294813546024733050135082024292481598322682990045855877556853392263676715734911232910368712575738786450510156105046776600566496799942574786503183241332740784997363514285857446938222302824964396227964711868412832852194845619628366554904150230665043909281603861298992421759553638135733037244888585600075655017766713763334284974682754159767494437867386464788270392548503256135412609157993954349845981674000072937143857040970855382655304911806719316346552101453584266121],
    [13, 13636547774903694433910615288816366243965221147245493790443257513469643051508482519945160993497983268746607032666514024577996510214003878851754244812785830861056511467944880656887067183093022088006603023892079757597903932697728395729605528467171403935076011715369931494813762896302405865063013876978950952553183445737415893862580946529557997177862386840671940665891984463553509323759394863514802662045074793125218445076375294720405008157895103559623204523371691063630903658360461001806917018298844432738514873530829540084732665560723768831816785580126848217585494349751859982707295270194451027637908966488433591336079],
    [13, 13422209706853784863425138450444393536114566510977689013118842078064352816867606066548879016746689784867031499069217146653949323203507755857385123653072875573743110808787259755688613540214185294636104765964080842615717180413731820679997453377899736419007193552970900617704671115646941207925636014254352661937769415565529244046272257822921740649781322893596978112103176487718960676212380426151079825140922318909470514158027009961239217428522970405297292867815726509360369236095377704967444339421311749405316999191339677904499413281713365474466679134722393111495793887387332928227905039036942450742103526490509249576159],
    [13, 21746430662648628292439055708644436184530740821098010749514133474681581832957631729292681550968108122182841907644832479495695011213810971334153360397292385819609198743433956578966857749821825621262178208409227379634952172419748956184624505995106932133301461499473823229623656490844764958301835433668618062743327682117611417235819168865744757242990985069648255779083246816509593018812991050741917153961245784296647661659339041115118272068392627299499703962645966495325055378652176922700072734325787550811454984878236039742147547963385471101805136506286953288566035101103034341742923072819774753918471775281464739904101],
    [13, 16012920802348742413202394765537959589119609441428117329692661212660781149297315973073063954731746455220386673231725950116051390914388279415796378305381377822621647264088603927560119754278978906758212463937071494263575443156089509654950881813861479449401068535285885349738367249035960528895049222211387021733152221289202030407416118814341241382479971018611239102343929419190892133819275458474489856666791981711793637127167775551296403296397810821548297674986394286293380472089135564385129140069501205054853729781710604489652713172579677128036322403868618295553335257593973027194532512596143733434234439677513237984107]
]


# == Day Time == #
package = [11348275592172789430802632398715397831929456592129727148350341695822097922745546634103895397114240780119492097879709874341733998189314701220819602086989170395665694216144611451695210776788208725517321710496401109614989729783280209806513298851774400705822274570042128297336679615535569295725037051009221966882907606741910671983811835353310553679554656322510247012465612842055583530354825164440556725066351429241835394579392892121937744444324723509039593320520073762479405487678614235658010109343868772211070874500834820005557924944766175445227592086997786601600141172729543326022039897279215360210475222205314199752358, 11817047514083750028443306573161291960303002458276716688201587284992675854178250185695613342603396451495053496021018943618684096193774851513377343785523373066637422156529843356640438514917147007662989366432951340073247573347091422478343675687872524102452812391963856179412214914106817415620613886827405526709334122157218264253412138947978859771457788135381194396144386611627935519990330309154612803264373276472523863776757124489507206744895878709136339189551422814752920383697719212261820943113370067423118794871570596583232694067119303936516491830190746798281923693136901268220982292626728815051587839682733501582997, 3131427695639074007646625687827523632044624200167725001731246731463369200890045250738898155425873822581405723445926216099453276470655307513244478613248253397941362848890729091875615893643288181126353294271063912991208029628896380928878098320509891044728414542705582996774991148116051162157848421643082210867849206627757941596203046799655123006406284498009424107637970927771132706399889289085811447333980744767367889464364519571965014435281718495338752896521777070285880327861778156398424643033288480056322928449210425585380975486759287881877636187364299666207762828705236236071045450767253946524067440138527952996304, 3345060634868343217881273515503289974894457362066685037297545772310131198850220025672843957153107490874807599311288876818421468275658855183857485067696603798636556327070411528170381402923911922437076616994460720931230980991440337397730061039967493443152767007916713160518618697678791358770766857737217910848181657393760417031865203943283074078341988117567851667858026108335625589177179258992930648353570238327435125409871028669479754623782967450462280802423233657422873275069133939005033872391235288329468886849808534906305377008408076775145268714146937205940659708210819711903273898505450411746796296074348301840443, 689229715602713064347690095007369004049337459458047359544160409565437783924368962797071453687950582019132146435134269723546824657132278724115055713024437048832952574546581164678912794341156478859615959289720931333010836265396177238403118182219901102453660596556053537987705012972371809213618745302576874122654094213771963420178465724399112964705426548207838941065298709968044913923423922781681311806180694571535910059881703228238538782302346351472443730399075812346657046097375387076507982673848430573754749554553794234945423901111974280859817600907619255722739374513108613738135872066592727564964404002462119084702]
# == Night Time == #
e = 65537
n = 19628814650078845889624476490795800811418703155298421183649751922179289373872110164946485468758965499898659860381452920316689731813466611171330082419646032975535828938381971760997472673267667258345915647828047467420412766203712358122436358120743184983881044132767579608354023899206025747277296489890315455139161247982158229333619416375842911027431739437723838483131248360727904613423834627213036877579164949084954352768932164210879329537266501942223360207803513487189832308290555832923018589686990981697562750385892888271329399531648035355662276186237232094775404084845357101354614900716614704579902047366473325519851
ciphertext = 18231770979476945075115454933498285687471248736331968136534439886998853983159878091479109027681230666670001308495054141682281492473521819495259722942633525843224223138121210743435008344491182811096997837681349401919300801071760448609909297020846949507707329708251861866061443743942558286917774317607571379516986051564317860557772153943821431899226380831989795907857566336085097807330399388077758869632230636727348278392968946952484442630549599469645903047917899063746000458656292320802815605327181346234519795519772619774175495201258591571744214020509439053957080210165266709953654561600989486386199867341092142358249
shell = 7450311459083436799013470526820816670296314417175130490433500468646960366746415074085735399822973890608046359739147553438015771999419943640758794686461655503899174274852006852675273759918109697488252918038788275865249305840107266839320745067341253227218580768443831238305064450748932813304412926315551102620477056031794884272260575749720364002093756539399717557808977458033683588388899534871439955606629530406662400672087729944642496842353084711242911328651341343429685261174338868058208644730980459845089948243884209259777439653298562832822410224626781415627048867272937969823329086437858777995321438386601575065665

简单分析一下，题目是由两个部分组成的，首先函数 day 生成了含有五个参数的数组 $A$，这五个会用到函数 night 里面参与 $shell$ 的计算，而 shell 与模数的因子 $p,q$ 相关。因此解题思路就很明确了，根据函数 day 的输出 $package$ 恢复数组 $A$，根据 $A$ 和 $shell$ 分解模数 $n$，最后解密 $ciphertext$ 获得明文 flag。

解题步骤

首先我们看到 $day$ 函数，其首先生成了 5 个大小为 $2^{30}$ 至 $2^{40}$ 的数，然后用 $||$ 符号做拼接得到 $hint$。如果觉得绕，可以本地跑一下

from Crypto.Util.number import *

def day():
    print("# == Day Time == #")
    A = [getRandomRange(1 << 30, 1 << 40) for _ in '01234']

    #from notebook import pubkeys
    hint = str(A)[1:-1].replace(', ', '||').encode()
    print(hint)
    # hint = bytes_to_long(pad(hint))
    # package = []
    # for pubkey in pubkeys:
    #     e, n = pubkey
    #     package.append(pow(hint, e, n))
    # print(f"{package = }")

    return A
day()

得到 b'146239978572||823596471040||1052171479378||849547394504||50672655347'，多试几次可以发现字符串的长度大约为 $67-70$，对应的最多也就是 560 个比特。

随后函数下面是将 $hint$ 填充至 2048 比特后，使用 notebook 中的公钥对其进行加密。看到 notebook 中的公钥

pubkeys = [
    [13, 16966923273393034574368601955241184391111444785998466710722972275633988040568029224272430397635357872449163107278928804572765398970752644900568552514020294813546024733050135082024292481598322682990045855877556853392263676715734911232910368712575738786450510156105046776600566496799942574786503183241332740784997363514285857446938222302824964396227964711868412832852194845619628366554904150230665043909281603861298992421759553638135733037244888585600075655017766713763334284974682754159767494437867386464788270392548503256135412609157993954349845981674000072937143857040970855382655304911806719316346552101453584266121],
    [13, 13636547774903694433910615288816366243965221147245493790443257513469643051508482519945160993497983268746607032666514024577996510214003878851754244812785830861056511467944880656887067183093022088006603023892079757597903932697728395729605528467171403935076011715369931494813762896302405865063013876978950952553183445737415893862580946529557997177862386840671940665891984463553509323759394863514802662045074793125218445076375294720405008157895103559623204523371691063630903658360461001806917018298844432738514873530829540084732665560723768831816785580126848217585494349751859982707295270194451027637908966488433591336079],
    [13, 13422209706853784863425138450444393536114566510977689013118842078064352816867606066548879016746689784867031499069217146653949323203507755857385123653072875573743110808787259755688613540214185294636104765964080842615717180413731820679997453377899736419007193552970900617704671115646941207925636014254352661937769415565529244046272257822921740649781322893596978112103176487718960676212380426151079825140922318909470514158027009961239217428522970405297292867815726509360369236095377704967444339421311749405316999191339677904499413281713365474466679134722393111495793887387332928227905039036942450742103526490509249576159],
    [13, 21746430662648628292439055708644436184530740821098010749514133474681581832957631729292681550968108122182841907644832479495695011213810971334153360397292385819609198743433956578966857749821825621262178208409227379634952172419748956184624505995106932133301461499473823229623656490844764958301835433668618062743327682117611417235819168865744757242990985069648255779083246816509593018812991050741917153961245784296647661659339041115118272068392627299499703962645966495325055378652176922700072734325787550811454984878236039742147547963385471101805136506286953288566035101103034341742923072819774753918471775281464739904101],
    [13, 16012920802348742413202394765537959589119609441428117329692661212660781149297315973073063954731746455220386673231725950116051390914388279415796378305381377822621647264088603927560119754278978906758212463937071494263575443156089509654950881813861479449401068535285885349738367249035960528895049222211387021733152221289202030407416118814341241382479971018611239102343929419190892133819275458474489856666791981711793637127167775551296403296397810821548297674986394286293380472089135564385129140069501205054853729781710604489652713172579677128036322403868618295553335257593973027194532512596143733434234439677513237984107]
]

可以看到，公钥指数都是 13，但是模数不同，因此对应 RSA 低加密指数广播攻击。不过直接攻击是不行的，因为 $hint$ 被填充到了 2048 比特，如果公钥指数是 13，那么就需要 13 对公钥对，以及对应的密文。这里的切入点在于 pad 函数

1 2	def pad(msg): return msg + b'\x00' * (2048 // 8 - len(msg))

pad 函数只是单纯的在 $msg$ 尾部加了 \x00，因此根据 RSA 加密公式 $m^e \equiv c \pmod n$，而 $m$ 可以写成 $m = m’ \cdot 2^x$ （这一部分没转过来的话可以看一下公众号文章密码学基础之进制与编码），其中 $x$ 我们可以用本地的数据测一下

from Crypto.Util.number import *

def pad(msg):
    return msg + b'\x00' * (2048 // 8 - len(msg))



def day():
    A = [getRandomRange(1 << 30, 1 << 40) for _ in '01234']
    hint = str(A)[1:-1].replace(', ', '||').encode()
    hint1 = bytes_to_long(hint)
    hint2 = bytes_to_long(pad(hint))
    print(hex(hint2//hint1))

    return A
day()

多测试几次，得到的结果是 0x1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 左右，为了具有普适性，我们可以稍微的减少一点，比如去掉两个或者四个 0，设为 $pad$

这样我们就可以先对密文进行处理 $(m’\cdot pad) ^ e \equiv c \pmod n \to m’^e \equiv c \cdot pad^{-e} \pmod n$

而由于 $m’$ 约为 560 比特，$560*\frac{13} {5} \lt 2048 $ ，即可使用中国剩余定理恢复 $hint$，（这一部分没转过来的话可以看一下公众号文章密码学基础之数论四大定理和密码学攻击之RSA：初见）从而获取数组 $A$ 的内容。

有了 $A$ 之后，我们需要根据 $shell$ 恢复分解 $n$，其中

1
2
3

core = getRandomRange(1 << 70, 1 << 80)
box = (A[4] * p ** 4 + A[3] * p ** 3 + A[2] * p ** 2 + A[1] * p ** 1 + core) % n
shell = (A[4] * box ** 4 + A[3] * box ** 3 + A[2] * box ** 2 + A[1] * box ** 1 + A[0]) % n

这里我们注意到，由于 $box \equiv core \pmod p$，因此 $shell \equiv A_4\cdot core^4+A_3\cdot core^3+A_2\cdot core^2+A_1\cdot core+A_0 \pmod p$

而由于 $core$ 只有 $70-80$ 比特，因此我们可以使用 copper 在模 p 下解出小根 $core$，有了 $core$ ，加上 $A$，根据
$$
shell \equiv A_4\cdot core^4+A_3\cdot core^3+A_2\cdot core^2+A_1\cdot core+A_0 \pmod p
$$
所以有
$$
shell = A_4\cdot core^4+A_3\cdot core^3+A_2\cdot core^2+A_1\cdot core+A_0 +kp
$$
因此直接计算 $GCD(shell-(A_4\cdot core^4+A_3\cdot core^3+A_2\cdot core^2+A_1\cdot core+A_0),n)$ 即可分解模数 $n$，从而解密密文获得 flag 了。

解题脚本

sagemath

from Crypto.Util.number import *
from gmpy2 import *

package = [11348275592172789430802632398715397831929456592129727148350341695822097922745546634103895397114240780119492097879709874341733998189314701220819602086989170395665694216144611451695210776788208725517321710496401109614989729783280209806513298851774400705822274570042128297336679615535569295725037051009221966882907606741910671983811835353310553679554656322510247012465612842055583530354825164440556725066351429241835394579392892121937744444324723509039593320520073762479405487678614235658010109343868772211070874500834820005557924944766175445227592086997786601600141172729543326022039897279215360210475222205314199752358, 11817047514083750028443306573161291960303002458276716688201587284992675854178250185695613342603396451495053496021018943618684096193774851513377343785523373066637422156529843356640438514917147007662989366432951340073247573347091422478343675687872524102452812391963856179412214914106817415620613886827405526709334122157218264253412138947978859771457788135381194396144386611627935519990330309154612803264373276472523863776757124489507206744895878709136339189551422814752920383697719212261820943113370067423118794871570596583232694067119303936516491830190746798281923693136901268220982292626728815051587839682733501582997, 3131427695639074007646625687827523632044624200167725001731246731463369200890045250738898155425873822581405723445926216099453276470655307513244478613248253397941362848890729091875615893643288181126353294271063912991208029628896380928878098320509891044728414542705582996774991148116051162157848421643082210867849206627757941596203046799655123006406284498009424107637970927771132706399889289085811447333980744767367889464364519571965014435281718495338752896521777070285880327861778156398424643033288480056322928449210425585380975486759287881877636187364299666207762828705236236071045450767253946524067440138527952996304, 3345060634868343217881273515503289974894457362066685037297545772310131198850220025672843957153107490874807599311288876818421468275658855183857485067696603798636556327070411528170381402923911922437076616994460720931230980991440337397730061039967493443152767007916713160518618697678791358770766857737217910848181657393760417031865203943283074078341988117567851667858026108335625589177179258992930648353570238327435125409871028669479754623782967450462280802423233657422873275069133939005033872391235288329468886849808534906305377008408076775145268714146937205940659708210819711903273898505450411746796296074348301840443, 689229715602713064347690095007369004049337459458047359544160409565437783924368962797071453687950582019132146435134269723546824657132278724115055713024437048832952574546581164678912794341156478859615959289720931333010836265396177238403118182219901102453660596556053537987705012972371809213618745302576874122654094213771963420178465724399112964705426548207838941065298709968044913923423922781681311806180694571535910059881703228238538782302346351472443730399075812346657046097375387076507982673848430573754749554553794234945423901111974280859817600907619255722739374513108613738135872066592727564964404002462119084702]
pubkeys = [
    [13, 16966923273393034574368601955241184391111444785998466710722972275633988040568029224272430397635357872449163107278928804572765398970752644900568552514020294813546024733050135082024292481598322682990045855877556853392263676715734911232910368712575738786450510156105046776600566496799942574786503183241332740784997363514285857446938222302824964396227964711868412832852194845619628366554904150230665043909281603861298992421759553638135733037244888585600075655017766713763334284974682754159767494437867386464788270392548503256135412609157993954349845981674000072937143857040970855382655304911806719316346552101453584266121],
    [13, 13636547774903694433910615288816366243965221147245493790443257513469643051508482519945160993497983268746607032666514024577996510214003878851754244812785830861056511467944880656887067183093022088006603023892079757597903932697728395729605528467171403935076011715369931494813762896302405865063013876978950952553183445737415893862580946529557997177862386840671940665891984463553509323759394863514802662045074793125218445076375294720405008157895103559623204523371691063630903658360461001806917018298844432738514873530829540084732665560723768831816785580126848217585494349751859982707295270194451027637908966488433591336079],
    [13, 13422209706853784863425138450444393536114566510977689013118842078064352816867606066548879016746689784867031499069217146653949323203507755857385123653072875573743110808787259755688613540214185294636104765964080842615717180413731820679997453377899736419007193552970900617704671115646941207925636014254352661937769415565529244046272257822921740649781322893596978112103176487718960676212380426151079825140922318909470514158027009961239217428522970405297292867815726509360369236095377704967444339421311749405316999191339677904499413281713365474466679134722393111495793887387332928227905039036942450742103526490509249576159],
    [13, 21746430662648628292439055708644436184530740821098010749514133474681581832957631729292681550968108122182841907644832479495695011213810971334153360397292385819609198743433956578966857749821825621262178208409227379634952172419748956184624505995106932133301461499473823229623656490844764958301835433668618062743327682117611417235819168865744757242990985069648255779083246816509593018812991050741917153961245784296647661659339041115118272068392627299499703962645966495325055378652176922700072734325787550811454984878236039742147547963385471101805136506286953288566035101103034341742923072819774753918471775281464739904101],
    [13, 16012920802348742413202394765537959589119609441428117329692661212660781149297315973073063954731746455220386673231725950116051390914388279415796378305381377822621647264088603927560119754278978906758212463937071494263575443156089509654950881813861479449401068535285885349738367249035960528895049222211387021733152221289202030407416118814341241382479971018611239102343929419190892133819275458474489856666791981711793637127167775551296403296397810821548297674986394286293380472089135564385129140069501205054853729781710604489652713172579677128036322403868618295553335257593973027194532512596143733434234439677513237984107]
]

n = []
for each in pubkeys:
    n.append(each[1])

pads = 0x1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

c = []
for index in range(len(package)):
    c += [int(package[index] * pow(pads,-13,n[index]) % n[index])]

hint = crt(c,n)
hint = long_to_bytes(iroot(hint,13)[0])
A = [646919678902,598613162045,90472013741,917100488664,838250498519]
n = 19628814650078845889624476490795800811418703155298421183649751922179289373872110164946485468758965499898659860381452920316689731813466611171330082419646032975535828938381971760997472673267667258345915647828047467420412766203712358122436358120743184983881044132767579608354023899206025747277296489890315455139161247982158229333619416375842911027431739437723838483131248360727904613423834627213036877579164949084954352768932164210879329537266501942223360207803513487189832308290555832923018589686990981697562750385892888271329399531648035355662276186237232094775404084845357101354614900716614704579902047366473325519851
shell = 7450311459083436799013470526820816670296314417175130490433500468646960366746415074085735399822973890608046359739147553438015771999419943640758794686461655503899174274852006852675273759918109697488252918038788275865249305840107266839320745067341253227218580768443831238305064450748932813304412926315551102620477056031794884272260575749720364002093756539399717557808977458033683588388899534871439955606629530406662400672087729944642496842353084711242911328651341343429685261174338868058208644730980459845089948243884209259777439653298562832822410224626781415627048867272937969823329086437858777995321438386601575065665
ciphertext = 18231770979476945075115454933498285687471248736331968136534439886998853983159878091479109027681230666670001308495054141682281492473521819495259722942633525843224223138121210743435008344491182811096997837681349401919300801071760448609909297020846949507707329708251861866061443743942558286917774317607571379516986051564317860557772153943821431899226380831989795907857566336085097807330399388077758869632230636727348278392968946952484442630549599469645903047917899063746000458656292320802815605327181346234519795519772619774175495201258591571744214020509439053957080210165266709953654561600989486386199867341092142358249

R.<box> = Zmod(n)[]
f = (A[4] * box ** 4 + A[3] * box ** 3 + A[2] * box ** 2 + A[1] * box ** 1 + A[0]) - shell
core = f.monic().small_roots(X=2^80,beta=0.4,epsilon=0.02)[0]


core = 72398025613557274548283
box = core
ff = shell - (A[4] * box ** 4 + A[3] * box ** 3 + A[2] * box ** 2 + A[1] * box ** 1 + A[0])
p = int(GCD(ff,n))
q = int(n//p)
phi = (p-1)*(q-1)
e = 65537
d = inverse(e,phi)
m = pow(ciphertext,d,n)
print(long_to_bytes(int(m)))

得到 b'Your flag is: flag{8d24d7d491106a7974d5afe9342b2834}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com